package algorithm.leetcode.I1to100;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个数组,输出该数组的全排列
 */

public class Q46 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        if (nums.length == 0) {
            return result;
        }

        int len = nums.length;
        boolean[] useMarker = new boolean[len];
        List<Integer> path = new ArrayList<>();

        // dfs(nums, len, 0, useMarker, path, result);
        dfs2(nums, len, useMarker, path, result);

        return result;

    }


    /**
     * 深度优先搜索
     * @param nums 常值,可尝试的数字
     * @param len 常值,用来判断递归是否结束
     * @param depth 树展开深度,也是当前解的长度,用来判断递归是否结束
     * @param useMarker 可尝试数字是否可用
     * @param path 当前解
     * @param res 所有可行解
     */
    private void dfs(int[] nums,
                     int len,
                     int depth,
                     boolean[] useMarker,
                     List<Integer> path,
                     List<List<Integer>> res) {
        // 终止条件:path为nums的一个全排列
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!useMarker[i]) {
                useMarker[i] = true;
                path.add(nums[i]);
                dfs(nums, len, depth+1, useMarker, path, res);
                path.remove(path.size()-1);
                useMarker[i] = false;
            }
        }
    }


    private void dfs2(int[] nums,
                     int len,
                     boolean[] useMarker,
                     List<Integer> path,
                     List<List<Integer>> res) {
        // 终止条件:path为nums的一个全排列
        if (path.size() == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!useMarker[i]) {
                useMarker[i] = true;
                path.add(nums[i]);
                dfs2(nums, len, useMarker, path, res);
                path.remove(path.size()-1);
                useMarker[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,2, 3};
        Q46 solution = new Q46();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }

}
